首先,其实我去年就在讨论区问过这个问题的,但是……没人理我……
就是这么个东西,一个普通的,带路径压缩的并查集
int n, f[N], counter = 0;
int fa(int x) {
counter++;
return f[x] == x ? x : f[x] = fa(f[x]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
f[i] = f[i-1] = i;
fa(rand() % i);
}
printf("%d\n", counter);
}
其中rand()返回的是均匀随机数,求输出的counter的数学期望
根据一波打表找规律发现答案是
证明:
定义合法树为:每个节点的编号均小于其父节点编号的树,那么:
- 对于每个随机序列,按照以上代码生成的树都是合法树
- 不同的随机序列有种
- 不同的合法树有种
- 对于每个合法树,都存在一个随机序列,使得按照以上代码能生成该树
简述下第四条的构造方法,对于一棵合法树,每次删除根节点,则剩下的子树里编号最小的点就是序列的最后一个点。把剩下的子树按照节点编号大小排序连成一条链,那么对该树上刚才找到的点进行路径压缩可以得到原树(如下图),且显然这样做剩下的树仍然是合法树,循环下去求即可

结合以上四条,可得:随机序列和合法树是一一对应的
那么我们要求的就是所有合法树上平均的答案,很容易递推
设为counter的期望,为点数为的合法树所有节点深度的平均值(根节点深度为),则有递推式
然后随便推两下就能求出来了
证毕